//class Solution {
//public:
//    int minFlipsMonoIncr(string s) {
//        int n = s.size();
//        vector<int> f(n + 1), g(n + 1);
//        for (int i = 1; i <= n; i++)
//        {
//            if (s[i - 1] == '1')
//            {
//                f[i] = f[i - 1] + 1;
//                g[i] = min(f[i - 1], g[i - 1]);
//            }
//            else
//            {
//                f[i] = f[i - 1];
//                g[i] = min(f[i - 1], g[i - 1]) + 1;
//            }
//        }
//        return min(f[n], g[n]);
//    }
//};
//


class Solution {
public:
    int hash[26] = { 0 };
    int characterReplacement(string s, int k) {
        int ret = 0, maxcount = 0;
        for (int left = 0, right = 0, count = 0; right < s.size(); right++)
        {
            int in = s[right] - 'A';
            maxcount = max(maxcount, ++hash[in]);
            while (right - left + 1 > maxcount + k)
            {
                int out = s[left++] - 'A';
                maxcount = max(maxcount, --hash[out]);
            }
            ret = max(ret, right - left + 1);
        }
        return ret;
    }
};